A common problem in image processing is to find primitives such as straight lines, circles, ellipses, and other higher order polynomials or any curve in frames of image data. One approach is to use a Hough transform. The Hough transform maps a point in the image array to a curve or surface in the transform domain that indicates the parameters of all primitives passing through the point. If the primitive is a straight line, the Hough transform of the entire input image is mathematically equivalent to a 2-dimensional discrete Radon transform or a Slant Stack transform. However, when computing a 2-dimensional discrete Radon transform or a Slant Stack transform it is usual to calculate the transform value at each point in the transform domain from a set of points in the image array.
Generalization of the Hough technique to other curves is straightforward and the method works for any curve s(x,p)=0 where x is a position vector of coordinates in the image array and p is a parameter vector of coefficients. The complexity of the Hough transform is strongly dependent on the number of coordinates and coefficients in a given representation. Further generalizations of the Hough transform to detect curves of no simple analytic representations are also possible.
The greatest advantage of Hough method for curve detection is its ability to overlook noisy points in the input data. Extremely noisy points will not change the accumulator values at parameter points of interest. Another advantage is that Hough method can be used to detect multiple curves of similar forms by searching for local maxima in the parameter space.
Calculation of the Hough transform is computationally expensive. This presents problem for real-time applications where rapid computation is required at a low cost. An example is the analysis of video frames from an automobile video camera, for applications such as vehicle guidance and license-plate reading. Another example is machine vision for robot applications. All of these applications require real-time processing of high data rate video frames.
Prior applications in this area have focused mainly on the design of algorithms for implementation on general-purpose processors, such as personal computers, digital signal processors or general-purpose image processors.
The Hough transform requires mapping a point in the image array to a curve or a surface in the transform array. There are two approaches to the computation of the Hough transform. The first approach is to use a large number of accumulators, one for each element in the transform array. This approach results in complex hardware, such as computer graphics cards. The second approach is to use a single accumulator and to store the transform array in a memory. This approach is slow because of the requirement to perform multiple read and write operations for each image pixel to move partial sums between the memory and the accumulator.
Parallel processing hardware has been proposed for computing a Hough transform. In one approach, an image comprising an array of pixel values is partitioned into multiple sub images. The transform of each sub image is computed by a separate processing engine, thereby allowing parallel computation. An example of this approach is described in U.S. Pat. No. 5,809,322 issued on Sep. 15, 1988, and titled “Apparatus and method for signal processing”, by Akerib; Avidan (Associate Computing Limited). It describes an application where the image data is partitioned among processors for image analysis routines including Hough transform. A disadvantage of this approach is that in some applications, only pixels corresponding to foreground elements in an image need to be processed. In these applications the number of computations varies linearly with the number of foreground pixels in the input data (the image). Depending upon the spatial distribution of foreground pixels, the workload may not be uniformly distributed among the processors. For example, some sub-images may have no foreground elements while other sub-images may contain only foreground pixels. This results in poor processor utilization. Further, the partial sums of the Hough transform are stored in memory. Since more than one processor may be updating the same physical memory then a shared memory mechanism (such as semaphores) must be used or a separate memory must be used for each processor. The former approach introduces more computational overhead, while the latter approach is more expensive and is not practical for high dimensional Hough transform spaces. Thus, partitioning the image into sub-images is only practical for low-resolution images or for detecting curves with a low number of parameters (such as straight lines).